// test binary tree's create print and delete.
#include <iostream>
#include <deque>
#include <stack>
#include "lib/binary_tree.h"

void PrintFromTopToBottom(BinaryTreeNode* root);
void PrintByLevel(BinaryTreeNode* root);
void Print(BinaryTreeNode* root);
void FindPath(BinaryTreeNode* root, int expectSum);
void FindPath(BinaryTreeNode* root, int expectSum,
        std::vector<int> &path, int currentSum);
void PreOrderIteratively(BinaryTreeNode* root);
void PreOrderRecursively(BinaryTreeNode* root);
void InOrderIteratively(BinaryTreeNode* root);
void InOrderRecursively(BinaryTreeNode* root);
void PostOrderIteratively(BinaryTreeNode* root);
void PostOrderRecursively(BinaryTreeNode* root);

void TestBinaryTree() {
    std::cout << "====================================" << std::endl;
    std::cout << "Test binary tree..." << std::endl;
    std::vector<int> nodes_vec = {1, 2, 3, 4, 5, 6, 7};
    std::cout << "create binary tree: " << std::endl;
    BinaryTreeNode* root = CreateBinaryTree(nodes_vec);
    std::cout << "print binary tree common: "<< std::endl;
    PrintBinaryTree(root);
    std::cout << "print binary tree from top to bottom: " << std::endl;
    PrintFromTopToBottom(root);
    std::cout << "print binary tree from top to bottom by level: " << std::endl;
    PrintByLevel(root);
    std::cout << "print binary tree zhizixing: " << std::endl;
    Print(root);
    std::cout << "delete binary tree: " << std::endl;
    DeleteBinaryTree(root);
}

void TestBinaryTreeWithParentNode() {
    std::cout << "====================================" << std::endl;
    std::cout << "Test binary tree with parent node..." << std::endl;
    std::vector<int> nodes_vec = {1, 2, 3, 4, 5, 6, 7};
    std::cout << "Create binary tree with parent node: " << std::endl;
    BinaryTreeWithParentNode* root = CreateBinaryTreeWithParentNode(nodes_vec);
    std::cout << "print binary tree with parent node common: "<< std::endl;
    PrintBinaryTree(root);
    std::cout << "delete binary tree with parent node: " << std::endl;
    DeleteBinaryTree(root);
}

int main() {
    TestBinaryTree();
    TestBinaryTreeWithParentNode();

    std::vector<int> nodes_vec1 = {10, 5, 12, 4, 7};
    BinaryTreeNode* root1 = CreateBinaryTree(nodes_vec1);
    std::cout << "print binary tree: " << std::endl;
    PrintBinaryTree(root1);
    std::cout << "print the path of sum is a expect value" << std::endl;
    FindPath(root1, 22);
    DeleteBinaryTree(root1);

    // 6种遍历
    std::vector<int> nodes_vec2 = {1, 2, 3, 4, 5, 6};
    BinaryTreeNode* root2 = CreateBinaryTree(nodes_vec2);
    std::cout << "print binary tree: " << std::endl;
    PrintBinaryTree(root2);
    std::cout << "PreOrderRecursively:" << std::endl;
    PreOrderRecursively(root2);
    std::cout << std::endl;
    std::cout << "InOrderRecursively:" << std::endl;
    InOrderRecursively(root2);
    std::cout << std::endl;
    std::cout << "PostOrderRecursively:" << std::endl;
    PostOrderRecursively(root2);
    std::cout << std::endl;

    std::cout << "PreOrderIteratively:" << std::endl;
    PreOrderIteratively(root2);
    std::cout << std::endl;
    std::cout << "InOrderIteratively:" << std::endl;
    InOrderIteratively(root2);
    std::cout << std::endl;
    std::cout << "PostOrderIteratively:" << std::endl;
    PostOrderIteratively(root2);
    std::cout << std::endl;
    DeleteBinaryTree(root2);
}

// 不分行从上到下打印二叉树
void PrintFromTopToBottom(BinaryTreeNode* root) {
    if (!root) {
        return;
    }
    std::deque<BinaryTreeNode*> dequeTreeNode;
    dequeTreeNode.push_back(root);
    while(!dequeTreeNode.empty()) {
        auto node = dequeTreeNode.front();
        dequeTreeNode.pop_front();
        std::cout << node->value << " ";
        if (node->left) {
            dequeTreeNode.push_back(node->left);
        }
        if (node->right) {
            dequeTreeNode.push_back(node->right);
        }
    }
    std::cout << std::endl;
}

// 分行从上到下打印二叉树
void PrintByLevel(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::deque<BinaryTreeNode*> dequeTreeNode;
    dequeTreeNode.push_back(root);
    int currentLevel = 1, nextLevel = 0;
    while(!dequeTreeNode.empty()) {
        auto treeNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();
        std::cout << treeNode->value << " ";
        if (treeNode->left) {
            dequeTreeNode.push_back(treeNode->left);
            nextLevel++;
        }
        if (treeNode->right) {
            dequeTreeNode.push_back(treeNode->right);
            nextLevel++;
        }
        currentLevel--;
        if (currentLevel == 0) {
            std::cout << std::endl;
            currentLevel = nextLevel;
        }
    }
    std::cout << std::endl;
}

// 之字形打印二叉树
void Print(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::stack<BinaryTreeNode*> stackTreeNode[2];
    int currentLevel = 0, nextLevel = 1;
    stackTreeNode[currentLevel].push(root);
    while (!stackTreeNode[currentLevel].empty()) {
        auto treeNode = stackTreeNode[currentLevel].top();
        stackTreeNode[currentLevel].pop();
        std::cout << treeNode->value << " ";
        if (currentLevel == 1) {
            if (treeNode->right) {
                stackTreeNode[nextLevel].push(treeNode->right);
            }
            if (treeNode->left) {
                stackTreeNode[nextLevel].push(treeNode->left);
            }
        } else {
            if (treeNode->left) {
                stackTreeNode[nextLevel].push(treeNode->left);
            }
            if (treeNode->right) {
                stackTreeNode[nextLevel].push(treeNode->right);
            }
        }
        if (stackTreeNode[currentLevel].empty()) {
            std::cout << std::endl;
            currentLevel = 1 - currentLevel;
            nextLevel = 1 - nextLevel;
        }
    }
}

// 二叉树中和为某一值的路径
void FindPath(BinaryTreeNode* root, int expectSum) {
    if (root == nullptr) {
        return;
    }
    std::vector<int> path;
    FindPath(root, expectSum, path, 0);
}

void FindPath(BinaryTreeNode* root, int expectSum,
        std::vector<int> &path, int currentSum) {
    if (root == nullptr) {
        return;
    }
    currentSum += root->value;
    path.push_back(root->value);
    if (!root->left && !root->right && currentSum == expectSum) {
        for (size_t i = 0; i < path.size(); i++) {
            std::cout << path[i] << " ";
        }
        std::cout << std::endl;
    }
    if (root->left)
        FindPath(root->left, expectSum, path, currentSum);
    if (root->right)
        FindPath(root->right, expectSum, path, currentSum);

    currentSum -= root->value;
    path.pop_back();
}

// 二叉树遍历（递归）
void PreOrderRecursively(BinaryTreeNode* root) {
  if (root) {
    std::cout << root->value << ' ';
    PreOrderRecursively(root->left);
    PreOrderRecursively(root->right);
  }
}
void InOrderRecursively(BinaryTreeNode* root) {
  if (root) {
    InOrderRecursively(root->left);
    std::cout << root->value << ' ';
    InOrderRecursively(root->right);
  }
}
void PostOrderRecursively(BinaryTreeNode* root) {
  if (root) {
    PostOrderRecursively(root->left);
    PostOrderRecursively(root->right);
    std::cout << root->value << ' ';
  }
}

// 二叉树遍历（循环）
void PreOrderIteratively(BinaryTreeNode* root) {
  std::stack<BinaryTreeNode*> helper_stack;
  BinaryTreeNode* cur = root;
  while (cur != nullptr || !helper_stack.empty()) {
    while (cur != nullptr) {
      helper_stack.push(cur);
      std::cout << cur->value << ' ';
      cur = cur->left;
    }
    cur = helper_stack.top();
    helper_stack.pop();
    cur = cur->right;
  }
}
void InOrderIteratively(BinaryTreeNode* root) {
  std::stack<BinaryTreeNode*> helper_stack;
  BinaryTreeNode* cur = root;
  while (cur != nullptr || !helper_stack.empty()) {
    while (cur != nullptr) {
      helper_stack.push(cur);
      cur = cur->left;
    }
    cur = helper_stack.top();
    helper_stack.pop();
    std::cout << cur->value << ' ';
    cur = cur->right;
  }
}
void PostOrderIteratively(BinaryTreeNode* root) {
  std::stack<BinaryTreeNode*> helper_stack;
  BinaryTreeNode* cur = root;
  BinaryTreeNode* pre = nullptr;
  while (cur != nullptr || !helper_stack.empty()) {
    while (cur != nullptr) {
      helper_stack.push(cur);
      cur = cur->left;
    }
    cur = helper_stack.top();
    if (cur->right != nullptr && cur->right != pre) {
      cur = cur->right;
    } else {
      helper_stack.pop();
      std::cout << cur->value << ' ';
      pre = cur;
      cur = nullptr;
    }
  }
}
